(1) Field of the Invention
The present invention relates to a compiler that translates a source program into an object program, i.e. a machine code program. More particularly, the present invention relates to a compiler apparatus and a method used by a compiler apparatus to determine locations for variables in a memory area.
(2) Description of the Related Art
With the recent trend for larger-scale software, it becomes common to write software in high-level languages, such as C and C++, which are suitable for developing a larger-scale system.
Before loaded onto memory and executed, source programs written in a high-level language need to be translated into machine language codes by compilers dedicated for each source language so as to be directly executable by a CPU. A program loaded to memory includes, sets each composed of a code representing an instruction and a data item representing a variable. Each instruction represented by a code is executed by referencing a corresponding data item.
Here, there are two types of variables represented by data items. One is a global variable for which memory area is reserved at all times throughout run-time of the program, and the other is an automatic variable for which memory area (stack area) is reserved at the time when a predetermined function is called. Hereinafter, an “automatic variable” is simply referred to as a “variable”.
A compiler determines locations in a stack area for each variable that corresponds to a predetermined function. FIG. 12 is a flowchart of location determination processing according to a conventional scheme 1 performed by a compiler to determine locations in a stack area for storing variables.
First, the compiler reads a source program (step S1), and performs parsing of the construction of sentences constituting the read program (step S2), and generates a variable correspondence table that contains variables to be allocated to the stack area (step S3).
Here, the variable correspondence table shows, for each variable contained, its variable type, variable name, data size, and alignment. Note that a “data size” is hereinafter referred to simply as a “size”.
“Alignment” is a value predetermined according to each variable type and shows the strength of a constraint on a location in a stack area to which a corresponding variable is permitted to be allocated. For example, a variable having alignment “2” must be allocated to a location in a stack area whose address is a multiple of 2, and a variable having alignment “4” must be allocated to a location in a stack area whose address is a multiple of 4.
FIG. 4 is a view showing an example of the variable correspondence table. In the example shown in FIG. 4, the variable correspondence table contains four variable types (char, int, char[ ], and double [ ]) and shows corresponding variable names, sizes, and alignment values.
The compiler regards variables contained in the variable correspondence table as a target-variable set to be allocated to the stack area (step S4). The compiler selects from the target-variable set, a smallest-size variable, and determines a location in the stack area for the selected variable (step S5). The compiler then judges whether all of the variables in the target-variable set have been determined their locations in the stack area (step S6).
When judging that locations have been determined for all of the variables (step S6: Y), the compiler terminates the processing. On the other hand, when judging that any of the variables has not yet been determined its location (step S6: N), the compiler goes back to the step S5.
For example, when the variables contained in the variable correspondence table shown in FIG. 4 constitute a target-variable set, the compiler determines to allocate each variable to a location in a stack area as shown in a schematic diagram of FIG. 13. In FIG. 13, each-variable is determined to be allocated in the stack area in the ascending order of size (in the order of a, b, c and then d).
Here, each cell in FIG. 13 can store a one-byte variable. The first cell on the top left is assigned an address 0, the cell that is immediately to the right of the first cell is assigned an address 1, the cell that is immediately to the right of the second cell is assigned an address 2, and the cell that is immediately below the first cell is assigned an address 8. Note that the same description applies to later-described schematic diagrams showing locations of variables.
In FIG. 13, the spaces remaining unused in the stack area are where no variables are allocated due to the alignment constraints. To be more specific, the alignment of the variable b is 4. Consequently, the compiler is prohibited from allocating the variable b to a location at the address 1, i.e. immediately next to the variable a, and thus allocates the variable b to a location at the address 4. Similarly, the variable d is allocated to a location at the address 16.
With this memory allocation, when a variable stored within, for example, the first 32 bytes of the stack area is accessible with a single instruction, three are three different type variables each of which is accessible with a single instruction.
As described above, when variables are determined to be allocated in a stack area in the ascending order of size, a faster processing speed is achieved especially in the case of a program in which small-sized variables are frequently referenced.
Further, there is a conventional scheme 2 which determines to allocate variables to a stack area in the descending order of alignment.
FIG. 14 is a flowchart of location determination processing according to the conventional scheme 2 performed by a compiler to determine locations of variables in a stack area.
The compiler reads a source program (step S11); performs parsing of the construction of sentences constituting the read program (step S12); generates, based on the result of parsing, a variable correspondence table that contains variables to be allocated to the stack area (step S13); regards variables in the variable correspondence table as a target-variable set to be allocated to the stack area (step S14); selects, from the target-variable set, a variable having a largest alignment value and determines a location in the stack area for the selected variable (step S15); and judges whether all of the variables in the target-variable set have been determined their locations in the stack area (step S16).
When judging that locations have been determined for all of the variables (step S16: Y), the compiler terminates the processing. On the other hand, when judging that any of the variables has not yet been determined its location (step S16: N), the compiler goes back to the step S15.
For example, when the variables contained in the variable correspondence table shown in FIG. 4 constitute a target-variable set, the compiler determines to allocate each variable to a location in the stack area as shown in a schematic diagram shown in FIG. 15. In FIG. 15, each variable is determined to be allocated in the stack area in the descending order of alignment (in the order of d, b, c and then a (the order of c and a may be reversed)).
As shown in FIG. 15, according to this scheme, the compiler manages to allocate the variables in the stack area without leaving a unused space between adjacent variables.
As described above, memory allocation in the descending order of alignment minimizes a wasted, unused memory, and thus variables are effectively stored in a smaller capacity stack area.
Unfortunately, however, both conventional schemas have the following problems. Memory allocation according to the conventional scheme 1 inevitably results in that some of the stack area remains unused and thus wasted. As a result, a greater memory capacity is required.
Memory allocation according to the conventional scheme 2 tends to allocate a large-size variable at the top of the stack area, and thus fewer variables are accessible with a single instruction. This leads to decrease processing speed especially in the case of a program in which variables having smaller alignment are frequently referenced.